1. Stacks
Creating Stacks
Adding Elements
Removing Elements
2. Queues
Creating Queues
Adding Elements
Removing Elements
Table of Contents
2
3
sli.do
#python-advanced
Have a Question?
LIFO
Stacks
A stack is a linear data structure that stores items
The process of adding data to a stack is referred
to as a "push"
Retrieving data from a stack is called a "pop"
Elements in a stack are added/removed from the
top ("last in first, first out") or LIFO order
What is a Stack?
5
210
5
6
Push to a Stack
0
Count:
123
2
10
5
Count:
3
1
2
7
Pop from a Stack
The list methods make it very easy to use a list as a
stack
To add an item to the top of the stack, use
append()
To retrieve an item from the top of the stack, use
pop()
Stacks in Python
8
stack = [3, 4, 5]
stack.append(6)
stack.append(7)
print(stack) # [3, 4, 5, 6, 7]
stack.pop() # 7
print(stack) # [3, 4, 5, 6]
stack.pop() # 6
stack.pop() # 5
print(stack) # [3, 4]
Stacks in Python: Example
9
Stacks and Queues
Write a program that reads a string, reverses it using stacks
and prints the result on the console
Problem: Reverse Strings
seueuQ dna skcatS
I love Python
nohtyP evol I
10
text = list(input())
stack = []
for i in range(len(text)):
stack.append(text.pop())
print("".join(stack))
Solution: Reverse Strings
11
1 + (2 - (2 + 3) * 4 / (3 + 1)) * 5
We are given an arithmetic expression with brackets
Scan through the string and extract each sub-expression
Print the result back at the terminal
Problem: Matching Brackets
(2 + 3)
(3 + 1)
(2 - (2 + 3) * 4 / (3 + 1))
12
text = input()
brackets = []
for i in range(len(text)):
if text[i] == "(":
brackets.append(i)
elif text[i] == ")":
start_index = brackets.pop()
print(text[start_index:i + 1])
Solution: Matching Brackets
13
FIFO
Queues
A queue is a first-in first-out (FIFO) abstract data
type
We use them when we want things to happen in
the order that they were called
What is Queue?
15
-315121
32
1
0
4
5
Count:
16
Enqueue
423
5
Count:
-315121
17
Dequeue
It is possible to use a list as a queue, however they
are not efficient for this purpose
Doing inserts or pops from the beginning of a list
is slow
That's why we use collections.deque
We use append() to add to the queue and
popleft() to remove from the queue
Queues in Python
18
from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry") # Terry arrives
queue.append("Graham") # Graham arrives
queue.popleft() # First leaves: 'Eric'
queue.popleft() # Second leaves: 'John'
print(queue) # ['Michael', 'Terry', 'Graham']
Queues in Python: Example
19
Read an input with a name and adds it to a queue until
"End"
If you receive "Paid", print every customer and empty the
queue
When you receive "End" print the remaining people in the
format: "{count} people remaining."
Anna
Michael
Simone
End
Problem: Supermarket
3 people remaining.
20
from collections import deque
queue = deque()
while True:
command = input()
if command == "Paid":
while len(queue):
print(queue.popleft())
elif command == "End":
print(f"{len(queue)} people remaining.")
break
else:
queue.append(command)
Solution: Supermarket
21
Read the problem description from the Lab Documents and
test with the provided inputs
2
Peter
Amy
Start
2
refill 1
1
End
Problem: Water Dispenser
Peter got water
Amy got water
0 liters left
22
create a queue
read command
while command != Start:
append to queue and read new command
read command
while command != End:
if command == refill: increase litters
else: print message depending on the available litters
print left litters
Pseudocode: Water Dispenser
23
Live Exercise in Class (Lab)
Practice
25
Stack
LIFO data structure
Queue
FIFO data structure
Stack and Queue in Python
Summary
Software University – High-Quality Education,
Profession and Job for Software Developers
softuni.bg, softuni.org
Software University Foundation
softuni.foundation
Software University @ Facebook
facebook.com/SoftwareUniversity
Software University Forums
forum.softuni.bg
Trainings @ Software University (SoftUni)
28
